Hi, the next sampling method that we're going to look at is rejection sampling. Rejection

sampling is still in this category here. So we look at prox-leg Monte Carlo methods. And

in contrast to important sampling, rejection sampling gives us samples from a given measure

mu and not just a method of computing integrals. And for a notation that let's call mu this

probability measure that we want to sample from and in order for rejection sampling to

work we need a second probability measure just as we need it for important sampling

with the same prerequisites. So mu has to be absolutely continuous with respect to mu.

I will often call mu the reference measure. And we have to be able to evaluate the corresponding

radon-necodym density, r of x. And we need to be able to sample efficiently from mu.

If those two conditions are given then we need a third one. The third one is that we

need to be able to find a number, a finite number, so in particular this has to be less

than infinity such that this density is bounded from above by m. And the idea of rejection

sampling is really easy and works like this. First sample from the reference measure, call

this x, then accept this sample with a probability given by r of x divided by m. Because r of

x is bounded from above by m, this is a number between 0 and 1. And with this probability

we accept this sample. If it's accepted then this is our sample. If it's rejected then

we try again. We try to sample from mu again, then we again compute this number here, then

accept it with some probability and so on. So in pseudocode this looks like this. We

need a sample generator for the reference measure, we need density and we need this

positive number, sorry, m not r, such that r of x is bounded from above by this number.

This gives us one sample from mu. It works like this. First generate a new sample from

the reference measure, then generate a random number between 0 and 1, then evaluate this

number alpha here, and if this random number is less or equal than this number alpha, then

we accept x as a sample. So this u here is just, so what we want to do is we want to

be able to accept this with probability r of x divided by m. So there's another random

step here. First there's randomness coming in from the sample, then there's another sort

of randomness with which we accept this sample. So there needs to be a second source of randomness.

This is this uniform random value u. Why does this work? Let's draw this, the line 0, 1.

Let's say alpha is large, so maybe 90% or so. So if we draw this and we sample u in

this interval, then with 90% probability, u will be between 0 and alpha, so less than

alpha. If that's the case, then we accept, right? And then with this mechanic, we get

random acceptance with a specified probability of acceptance alpha, right? By this mechanism.

Okay, why should this work? It looks too simple to work, but there's one beautiful idea behind

this. This is something that you could call geometric sampling. I don't think that's

a name that exists, but I think it's a fitting name. And geometric sampling works like this.

So let's assume that for simplicity, the density of the measure we want to sample from has

compact support, so it fits inside a box, right? So this is the density from which we

want to sample. And now we draw this density on a piece of wood. So we draw this on some

board and then we hang this on the wall somewhere, and then we take a few steps back, and then

we randomly throw darts on this board, assuming that we are able to uniformly throw darts.

If we can do this, then we do this, and then we get darts on this board. And now we accept

only those samples or those darts, which are below the graph. And then we record the x

components here, here, here. And this constitutes a sequence of samples from this density. So

why does this work? Intuitively, for a given x position, the higher the density is, the

higher is the probability of acceptance. So we get more samples in a region where the

density is higher, as you can see here, right? So there are more samples here than here because

the density is higher here. And if the graph dips really low, then it's almost impossible

to get a randomly thrown dart below this line. So this is intuitively why this works. We

could prove this, but this gives a good picture. Now, there's a problem if this density, so

this is d mu divided by dx, if this is too concentrated. So what if mu looks like this?